package com.zwj.interview.链表;

/**
 * @Author: Zwj
 * @Date: 2022/9/15 14:05
 *
 *
 */
public class K个一组反转链表 {

    ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        //使用区间 [a, b)来维护k个待反转元素
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case
            if (b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素,比如：1->2->3->4->5->6,调用后返回2，原来的头结点1指向 下一组翻转后的头结点
        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }


    /**
     * 反转区间 [a, b) 的元素，注意是左闭右开
     */
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null;
        ListNode cur = a;
        ListNode next=a;
        // while 终止的条件改一下就行了
        while (cur != b) {
            next = cur.next;
            //执行反转
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 返回反转后的头结点
        return pre;
    }





}